package com.Algorithm.leetcode.Study;

/**
 * Created with IntelliJ IDEA.
 *
 * @Author: zjz
 * @Date: 2021/10/18/8:50
 * @Description: 使用快慢指针判断,快指针走两步,慢指针走一步,快指针遇到null就返回-1,表示没有环,如果有环,那必然快慢会相遇
 * @Target:判断有没有环
 */


public class 判断有没有环 {

}


class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
        next = null;
    }
}


/*
*  回忆下链表的结构 --Node0(val,next)-->Node1(val,next)-->Node2(val,next)--->Node3(val,null)------
*  实际上Node0为头节点(Node0(val,Node1(val,Node2(val,Node3(val,null))))
* */


class Solution {
    public boolean hasCycle(ListNode head) {


        boolean flag = false;


/*
* 如果不使用快慢指针,有环旧无限循环,不停..
*
* */

        while (head==null||head.next==null||head.next.next==null){
            return false;
        }

        if(head.next==head){
            return true;
        }

        ListNode cur = head;       // 表示当前节点,此处为head,下面需要不断变换
        ListNode quickNode = cur.next.next;  // 快指针,先走两步
        ListNode slowNode = cur.next;  // 慢指针,先走一步

            while (quickNode!=slowNode&&quickNode!=null){
                quickNode = quickNode.next.next;
                slowNode = slowNode.next;
                if (quickNode.next==null&&quickNode.next.next==null){
                    flag =  false;  // 无环
                }
                    flag =  true;
            }


        return flag;
    }
}
